home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / networking / appletalk / uab.shar / hash.c < prev    next >
C/C++ Source or Header  |  1990-07-12  |  21KB  |  792 lines
  1. static char rcsid[] = "$Author: cck $ $Date: 88/09/14 10:19:36 $";
  2. static char rcsident[] = "$Header: /src/local/mac/cap/etalk/RCS/hash.c,v 1.14 88/09/14 10:19:36 cck Rel $";
  3. static char revision[] = "$Revision: 1.14 $";
  4.  
  5. /*
  6.  * hash.h - external definitions for hash.c - generalized hashing function
  7.  *
  8.  *  written by Charlie C. Kim
  9.  *     Academic Networking, Communications and Systems Group
  10.  *     Center For Computing Activities
  11.  *     Columbia University
  12.  *   September 1988
  13.  *
  14.  *
  15.  * Copyright (c) 1988 by The Trustees of Columbia University 
  16.  *  in the City of New York.
  17.  *
  18.  * Permission is granted to any individual or institution to use,
  19.  * copy, or redistribute this software so long as it is not sold for
  20.  * profit, provided that this notice and the original copyright
  21.  * notices are retained.  Columbia University nor the author make no
  22.  * representations about the suitability of this software for any
  23.  * purpose.  It is provided "as is" without express or implied
  24.  * warranty.
  25.  *
  26.  *
  27.  * Edit History:
  28.  *
  29.  *  Sept 5, 1988  CCKim Created
  30.  *  Sept 6, 1988  CCKim Finished: level 0
  31.  *
  32. */
  33.  
  34. static char columbia_copyright[] = "Copyright (c) 1988 by The Trustees of \
  35. Columbia University in the City of New York";
  36.  
  37. #include <stdio.h>
  38. #include <sys/types.h>
  39. #include "hash.h"
  40.  
  41. #ifndef FALSE
  42. # define FALSE 0
  43. #endif
  44. #ifndef TRUE
  45. # define TRUE 1
  46. #endif
  47. #ifndef PRIVATE
  48. # define PRIVATE static
  49. #endif
  50.  
  51.  
  52. /*
  53.  * holds and describes a hash table
  54.  *
  55.  * ht_policy: policy on collisions (cf hash.h)
  56.  * ht_cfunc: takes (key, data) and returns true if they are equal
  57.  * ht_afunc: takes a key and returns the item from higher up
  58.  * ht_cpfunc: should compress the key to a integer -- only required if
  59.  *    no hash function has been provided
  60.  * ht_hfunc: takes (M, data) as arguments - returns hash index
  61.  *    M is the sizeof(int)*8 - log of the table size if the hashing
  62.  *     type is multiplicative
  63.  * ht_hfunc2: is the secondary hashing function for double hashing
  64.  * ht_chainops: chaining function other than linked list
  65.  * ht_stats: describes performance of hash table
  66.  * ht_type: hash function type
  67.  * ht_buckets: pointer to the hash table buckets
  68.  *
  69. */
  70. typedef struct htable {
  71.   int ht_M;            /* # of hash table buckes */
  72.   int ht_logM;            /* M or log M (for certain hash types) */
  73.   int ht_policy;        /* hashing policies for collision */
  74.   /* alway call with passed key first, data item second */
  75.   int (*ht_cfunc)();        /* comparision function */
  76.   caddr_t (*ht_afunc)();    /* allocate function */
  77.   u_int (*ht_cpfunc)();        /* compression function */
  78.   u_int (*ht_hfunc)();        /* hashing function */
  79.   u_int (*ht_hfunc2)();        /* secondary hashing function */
  80.   struct hash_bucket_list_ops *ht_chainops; /* chain functions */
  81.   int ht_type;            /* hash type */
  82.   struct hash_statistics ht_stats; /* statisitics */
  83.   caddr_t *ht_buckets;        /* actual hash table */
  84. } HTABLE;
  85.  
  86. /* some hash functions */
  87. PRIVATE u_int hash_multiplicative();
  88. PRIVATE u_int hash_division();
  89. PRIVATE u_int hash2_multiplicative();
  90. PRIVATE u_int hash2_division();
  91.  
  92. /* list operations */
  93. PRIVATE caddr_t list_find();
  94. PRIVATE caddr_t list_insert();
  95. PRIVATE int list_delete();
  96. PRIVATE caddr_t list_get();
  97.  
  98. /* basic hash bucket chaining with an ordered link list */
  99. PRIVATE struct hash_bucket_list_ops hash_chain_by_list = {
  100.   list_find,
  101.   list_insert,
  102.   list_delete,
  103.   list_get
  104. };
  105.  
  106. /* table of primary hashfunctions */
  107. PRIVATE u_int (*hash_funcs[HASH_TYPE_NUM])() = {
  108.   NULL,
  109.   hash_division,
  110.   hash_multiplicative,
  111. };
  112.  
  113. /* table of secondary hash functions */
  114. PRIVATE u_int (*hash_funcs2[HASH_TYPE_NUM])() = {
  115.   NULL,                /* own */
  116.   hash2_division,
  117.   hash2_multiplicative,
  118. };
  119.  
  120. /* free a hash table - free_func gets called to free data */
  121. void
  122. h_free(ht, free_func)
  123. HTABLE *ht;
  124. int (*free_func)();
  125. {
  126.   caddr_t *bt;
  127.   caddr_t p;
  128.   int M, i, policy;
  129.   caddr_t (*get_func)();
  130.   
  131.   M = ht->ht_M;            /* get # of entries */
  132.   bt = ht->ht_buckets;        /* get buckets */
  133.   ht->ht_buckets = NULL;    /* just in case... */
  134.   if (ht->ht_chainops)
  135.     get_func = ht->ht_chainops->hlo_get;
  136.   policy = ht->ht_policy;
  137.   if (bt == NULL)
  138.     return;
  139.   for (i = 0; i < M; i++) {
  140.     if (bt[i] == NULL)
  141.       continue;
  142.     switch (policy) {
  143.     case HASH_POLICY_CHAIN:
  144.       if (get_func == NULL)
  145.     break;
  146.       while ((p = (*get_func)(&bt[i])))
  147.     if (free_func)
  148.       (*free_func)(p);
  149.       break;
  150.     default:
  151.     if (free_func)
  152.       (*free_func)(bt[i]);
  153.     }
  154.   }
  155.   free((caddr_t)bt);            /* free old table */
  156.   free((caddr_t)ht);
  157. }
  158.  
  159. /* setup a new hash table, returns handle for hash table */
  160. caddr_t
  161. h_new(policy, hashtype, M, cfunc, afunc, cpfunc, hfunc, hfunc2, chainops)
  162. int policy;
  163. int hashtype;            /* hash type */
  164. int M;
  165. int (*cfunc)();            /* comparision function */
  166. caddr_t (*afunc)();            /* allocate function */
  167. u_int (*cpfunc)();        /* compression function */
  168. u_int (*hfunc)();        /* hash function */
  169. u_int (*hfunc2)();        /* secondary hash function */
  170. struct hash_bucket_list_ops *chainops;
  171. {
  172.   HTABLE *htable;
  173.  
  174.   if (cfunc == NULL) {        /* required! */
  175.     fprintf(stderr, "hash table create: no compare function\n");
  176.     return(NULL);
  177.   }
  178.   if (!HASH_TYPE_VALID(hashtype)) {
  179.     fprintf(stderr, "hash table create: invalid type %d\n", hashtype);
  180.     return(NULL);
  181.   }
  182.   if (hashtype == HASH_TYPE_OWN && hfunc == NULL) {
  183.   fprintf(stderr, "hash table create: must give hash function when own set\n");
  184.   return(NULL);
  185.   }
  186.   if (!HASH_POLICY_VALID(policy)) {
  187.     fprintf(stderr, "hash table create: invalid policy %d\n", policy);
  188.     return(NULL);
  189.   }
  190.   if (M <= 0) {
  191.     fprintf(stderr, "hash table create: invalid hash table size %d\n", M);
  192.     return(NULL);
  193.   }
  194.   if ((htable = (HTABLE *)malloc(sizeof(HTABLE))) == NULL)
  195.     return(NULL);
  196.   htable->ht_policy = policy;
  197.   htable->ht_cfunc = cfunc;
  198.   htable->ht_afunc = afunc;
  199.   htable->ht_hfunc = hash_funcs[hashtype];
  200.   if (htable->ht_policy == HASH_POLICY_DOUBLE_HASH)
  201.     htable->ht_hfunc2 = hash_funcs2[hashtype];
  202.   else
  203.     htable->ht_hfunc2 = NULL;
  204.   /* override std. hash functions if specified */
  205.   if (hfunc)
  206.     htable->ht_hfunc = hfunc;
  207.   if (hfunc2)
  208.     htable->ht_hfunc2 = hfunc2;
  209.   htable->ht_cpfunc = cpfunc;
  210.   htable->ht_chainops = chainops ? chainops : &hash_chain_by_list;
  211.   htable->ht_type = hashtype;
  212.   bzero(&htable->ht_stats, sizeof(htable->ht_stats));
  213.   htable->ht_stats.hs_buckets = M;
  214.   htable->ht_M = 0;        /* assume these */
  215.   return((caddr_t)h_redefine(htable,HASH_POLICY_OLD,HASH_TYPE_OLD, M,
  216.                  NULL, NULL,NULL,NULL, NULL, NULL));
  217. }
  218.  
  219. /* redefine an existing hash table, will rehash by creating new set of */
  220. /* buckets and killing off old set */
  221. caddr_t
  222. h_redefine(ht, policy, hashtype, M, cfunc, afunc, cpfunc, hfunc, hfunc2,
  223.        chainops)
  224. HTABLE *ht;
  225. int policy;            /* hashing policy */
  226. int hashtype;            /* hashing type */
  227. int M;                /* size */
  228. int (*cfunc)();            /* comparision function */
  229. caddr_t (*afunc)();        /* allocate function */
  230. u_int (*hfunc)();        /* hash function */
  231. u_int (*hfunc2)();        /* secondary hash function */
  232. u_int (*cpfunc)();        /* compression function */
  233. struct hash_bucket_list_ops *chainops;
  234. {
  235.   int logM, oldM, i, oldPolicy;
  236.   struct hash_bucket_list_ops *oldChainOps;
  237.   caddr_t *bt, *nbt;
  238.   caddr_t p;
  239.  
  240.   if (!HASH_TYPE_VALID(hashtype) && hashtype != HASH_TYPE_OLD) {
  241.     fprintf(stderr, "hash table create: invalid type %d\n", hashtype);
  242.     return(NULL);
  243.   }
  244.   if (!HASH_POLICY_VALID(policy) && policy != HASH_POLICY_OLD) {
  245.     fprintf(stderr, "hash table create: invalid policy %d\n", policy);
  246.     return(NULL);
  247.   }
  248.   if (M <= 0)            /* zero means base on old */
  249.     M = ht->ht_M;
  250.   if (hashtype == HASH_TYPE_OLD)
  251.     hashtype = ht->ht_type;    /* get old */
  252.   logM = 0;
  253.   switch (hashtype) {
  254.   case HASH_TYPE_MULTIPLICATIVE:
  255.     i = M >> 1;
  256.     M = 1;
  257.     logM = 0;
  258.     while (i) {            /* while M is still about */
  259.       i >>= 1;            /* divide by 2 */
  260.       M <<= 1;            /* multiply by 2 */
  261.       logM++;
  262.     }
  263.     break;
  264.   case HASH_TYPE_DIVISION:
  265.     M += (1 - (M%2));        /* make odd */
  266.     /* scale up M so it isn't relatively prime for these small primes */
  267.     /* c.f. Fundamental of Data Structures, Horowitz and Sahni, pp. 461 */
  268.     while (!((M%3) && (M%5) && (M%7) && (M%11) && (M%13) && (M%17)&&(M%19)))
  269.       M+=2;
  270.     break;
  271.   default:
  272.     break;
  273.   }
  274.   if (M <= ht->ht_M)        /* nothing to do */
  275.     return((caddr_t)ht);
  276.   if (logM == 0) {        /* no logM?  figure it */
  277.     int t = M>>1;        /* get M */
  278.     do {
  279.       logM++;            /* int log M to 1 */
  280.       t >>= 1;            /* divide by 2 */
  281.     } while (t);
  282.   }
  283.   bt = ht->ht_buckets;        /* get buckets */
  284.   oldM = ht->ht_M;
  285.   oldPolicy = ht->ht_policy;
  286.   oldChainOps = ht->ht_chainops;
  287.  
  288.   if ((nbt = (caddr_t *)calloc((u_int)M, sizeof(caddr_t))) == NULL) {
  289.     fprintf(stderr, "hash table create: no memory for %d element table\n",M);
  290.     return(NULL);        /* return */
  291.   }
  292.   ht->ht_buckets = nbt;    /* save new bucket table */
  293.   ht->ht_M = M;        /* assume these */
  294.   ht->ht_logM = logM;
  295.   ht->ht_stats.hs_buckets = M; /* mark # of buckets */
  296.   ht->ht_policy = (policy == HASH_POLICY_OLD) ? oldPolicy : policy;
  297.   if (afunc)
  298.     ht->ht_afunc = afunc;
  299.   if (cfunc)
  300.     ht->ht_cfunc = cfunc;
  301.   if (ht->ht_type != hashtype && hashtype != HASH_TYPE_OLD) {
  302.     ht->ht_hfunc = hash_funcs[hashtype];
  303.     if (ht->ht_policy == HASH_POLICY_DOUBLE_HASH)
  304.       ht->ht_hfunc2 = hash_funcs2[hashtype];
  305.     else
  306.       ht->ht_hfunc2 = NULL;
  307.   }
  308.   /* always reset if given */
  309.   if (hfunc)
  310.     ht->ht_hfunc = hfunc;
  311.   if (hfunc2)
  312.     ht->ht_hfunc2 = hfunc2;
  313.   if (cpfunc)
  314.     ht->ht_cpfunc = cpfunc;
  315.   if (chainops)
  316.     ht->ht_chainops = chainops;
  317.   ht->ht_type = hashtype;
  318.   {
  319.     struct hash_statistics *s = &ht->ht_stats;
  320.     /* no longer valid */
  321.     s->hs_used = s->hs_davg = s->hs_dsum = s->hs_dmax = 0;
  322.     /* no longer valid */
  323.     s->hs_lnum = s->hs_lsum = s->hs_lavg = 0;
  324.     /* cum. statistics stay */
  325.   }
  326.   /* rehash if new table */
  327.   if (bt) {
  328.     afunc = ht->ht_afunc;    /* save */
  329.     ht->ht_afunc = NULL;        /* turn off for a bit */
  330.     for (i = 0; i < oldM; i++) {
  331.       if (bt[i]) {
  332.     switch (oldPolicy) {
  333.     case HASH_POLICY_CHAIN:
  334.       while ((p = (*oldChainOps->hlo_get)(&bt[i])))
  335.         h_insert(ht, p);
  336.       break;
  337.     default:
  338.       h_insert(ht, bt[i]);
  339.     }
  340.       }
  341.     }
  342.     ht->ht_afunc = afunc;    /* turn back on */
  343.     free((caddr_t)bt);        /* free old table */
  344.   }
  345.   return((caddr_t)ht);
  346. }
  347.  
  348. /* update hash TABLE statistics: generally, these are off for chain */
  349. /* and when there are deletes done */ 
  350. PRIVATE int
  351. update_hash_table_stats(s, distance, updown)
  352. struct hash_statistics *s;
  353. int distance;
  354. int updown;
  355. {
  356.   if (distance > s->hs_dmax) /* new maximum distance */
  357.     s->hs_dmax = distance;
  358.   s->hs_dsum += distance;    /* bump sum of distances */
  359.   s->hs_used += updown;
  360.   if (s->hs_used)
  361.     s->hs_davg = (100*s->hs_dsum) / s->hs_used; /* scale it */
  362.   else
  363.     s->hs_davg = 0;
  364.   return(s->hs_davg);
  365. }
  366.  
  367. /* update lookup statisitics */
  368. PRIVATE int
  369. update_hash_lookup_stats(s, distance)
  370. struct hash_statistics *s;
  371. int distance;
  372. {
  373.   s->hs_lsum += distance;    /* bump sum of distances */
  374.   s->hs_lnum++;            /* bump number of distances */
  375.   s->hs_clsum += distance;    /* same for cum. */
  376.   s->hs_clnum++;
  377.   s->hs_lavg = (100*s->hs_lsum) / s->hs_lnum; /* save 2 decimal points */
  378.   return(s->hs_lavg);
  379. }
  380.  
  381. /* hash table operation: delete, insert, find */
  382. caddr_t
  383. h_operation(what, ht, key, idx, idx2, d, b)
  384. int what;
  385. HTABLE *ht;
  386. caddr_t key;
  387. int idx;            /* preliminary index (-1 if none) */
  388. int idx2;            /* secondary index (-1 if none) */
  389. int *d;                /* return distance ? */
  390. int *b;                /* return bucket # */
  391. {
  392.   int sidx, t;
  393.   int distance;
  394.   u_int cpkey;            /* compress version of key */
  395.   caddr_t *bp;            /* bucket pointer */
  396.   caddr_t *pbp = NULL;        /* previous bucket pointer for delete */
  397.   caddr_t data = NULL;
  398.  
  399.   /* blather */
  400.   if (ht == NULL || HASH_OP_INVALID(what))
  401.     return(NULL);
  402.   if (idx < 0) {
  403.     if (ht->ht_cpfunc) {
  404.       cpkey = (*ht->ht_cpfunc)(key);
  405.       idx = (*ht->ht_hfunc)(ht->ht_M, ht->ht_logM, cpkey);
  406.     } else
  407.       idx = (*ht->ht_hfunc)(ht->ht_M, ht->ht_logM, key);
  408.   }
  409.   sidx = idx;
  410.   if (ht->ht_buckets == NULL) {
  411.     fprintf(stderr, "No buckets for hash table!  (Possibly using a freed \
  412.  hash table handle)\n");
  413.     return(NULL);
  414.   }
  415.   bp = &ht->ht_buckets[idx];    /* start */
  416.   distance = 0;
  417.   if (b)
  418.     *b = sidx;
  419.  
  420.   if (ht->ht_policy == HASH_POLICY_CHAIN) {
  421.     caddr_t hint, hint2;
  422.  
  423.     /* distance should be updated */
  424.     data = (*ht->ht_chainops->hlo_find)(*bp,key,ht->ht_cfunc,
  425.                     &distance, &hint, &hint2);
  426.     switch (what) {
  427.     case HASH_OP_DELETE:
  428.       if (!data)
  429.     break;
  430.       /* key */
  431.       /* ignore error (should not happen!) */
  432.       (void)(*ht->ht_chainops->hlo_delete)(bp, key, &distance, hint, hint2);
  433.       update_hash_table_stats(&ht->ht_stats, -distance, -1);
  434.       break;
  435.     case HASH_OP_MEMBER:
  436.       if (data)
  437.     t = update_hash_lookup_stats(&ht->ht_stats, distance);
  438.       break;
  439.     case HASH_OP_INSERT:
  440.       if (data) {
  441.     t = update_hash_lookup_stats(&ht->ht_stats, distance);
  442.     break;
  443.       }
  444.       data= (*ht->ht_chainops->hlo_insert)(bp,key,ht->ht_afunc,
  445.                        &distance, hint,hint2);
  446.       update_hash_table_stats(&ht->ht_stats, distance, 1);
  447.       break;
  448.     }
  449.     if (d)
  450.       *d = distance;
  451.     return(data);
  452.   }
  453.  
  454.   do {
  455.     if (*bp == NULL) {
  456.       switch (what) {
  457.       case HASH_OP_DELETE:        /* finished delete */
  458.     break;
  459.       case HASH_OP_MEMBER:
  460.     data = NULL;
  461.     break;
  462.       case HASH_OP_INSERT:
  463.     /* left with insert */
  464.     data = ht->ht_afunc ? (*ht->ht_afunc)(key) : key;
  465.     *bp = data;
  466.     update_hash_table_stats(&ht->ht_stats, distance, 1);
  467.     break;
  468.       }
  469.       if (d)
  470.     *d = distance;
  471.       return(data);
  472.     } else {
  473.       switch (what) {
  474.       case HASH_OP_DELETE:
  475.     /* if we haven't found an key to delete, try to find it */
  476.     if (!pbp) {
  477.       if ((*ht->ht_cfunc)(key, *bp) == 0) {
  478.         data = *bp;        /* save return key */
  479.         *bp = NULL;        /* clear out this bucket */
  480.         pbp = bp;        /* remember this bucket */
  481.         update_hash_table_stats(&ht->ht_stats, -distance, -1);
  482.       }
  483.     } else {
  484.       /* delete old distance */
  485.       update_hash_table_stats(&ht->ht_stats, -distance, -1);
  486.       /* insert new distance */
  487.       update_hash_table_stats(&ht->ht_stats, distance-1, 1);
  488.       *pbp = *bp;        /* move bucket */
  489.       *bp = NULL;        /* clear out this bucket */
  490.       pbp = bp;        /* remember this bucket */
  491.     }
  492.       default:
  493.     if ((*ht->ht_cfunc)(key, *bp) == 0) {
  494.       t = update_hash_lookup_stats(&ht->ht_stats, distance);
  495.       if (d)
  496.         *d = distance;
  497.       return(*bp);        /* done */
  498.     }
  499.       }
  500.     }
  501.     if (idx2 < 0 && ht->ht_hfunc2)
  502.       if (ht->ht_cpfunc) 
  503.     idx2 = (*ht->ht_hfunc2)(ht->ht_M, ht->ht_logM, idx, cpkey);
  504.       else
  505.     idx2 = (*ht->ht_hfunc2)(ht->ht_M, ht->ht_logM, idx, key);
  506.     distance++;
  507.     idx += idx2 > 0 ? idx2 : 1; /* bump index */
  508.     bp++;            /* advance bucket pointer */
  509.     if (idx >= ht->ht_M) {    /* need to wrap around */
  510.       idx %= ht->ht_M;        /* push index about */
  511.       bp = &ht->ht_buckets[idx]; /* and reset buckets */
  512.     }
  513.   } while (sidx != idx);
  514.   return(NULL);
  515. }
  516.  
  517. /* return hash statistics */
  518. struct hash_statistics *
  519. h_statistics(h)
  520. HTABLE *h;
  521. {
  522.   return(&h->ht_stats);
  523. }
  524.  
  525.  
  526. /* for linked list */
  527. struct hash_chain_item {
  528.   struct hash_chain_item *hci_next; /* pointer to next item in chain */
  529.   caddr_t hci_data;        /* pointer to data */
  530. };
  531.  
  532. /*
  533.  * hint == previous(hint2)
  534.  *  hint2 is the match node or node whose data is > than current
  535.  *
  536. */
  537. PRIVATE caddr_t
  538. list_find(h, key, cmp, distance, hint, hint2)
  539. struct hash_chain_item *h;
  540. caddr_t key;
  541. int (*cmp)();
  542. int *distance;
  543. struct hash_chain_item **hint;
  544. struct hash_chain_item **hint2;
  545. {
  546.   struct hash_chain_item *hp = NULL;
  547.   int d,c;
  548.  
  549.   *distance = 0;        /* no distnace */
  550.   *hint = NULL;            /* mark no hint */
  551.   *hint2 = NULL;
  552.   if (h == NULL)
  553.     return(NULL);
  554.   for (d = 0 ; h ; h = h->hci_next) {
  555.     if ((c = (*cmp)(key, h->hci_data)) >= 0)
  556.       break;
  557.     d++;
  558.     hp = h;
  559.   }
  560.   if (distance)
  561.     *distance = d;
  562.   if (hint2)
  563.     *hint2 = h;
  564.   if (hint)
  565.     *hint = hp;
  566.   return(c == 0 ? h->hci_data : NULL);
  567. }
  568.  
  569. /*
  570.  * insert item into chain.  hint is from the lookup and helps us insert
  571.  * distance is from lookup too (we could choose to change)
  572.  *
  573.  * hint == previous(hint2)
  574.  *  hint2 is the match node or node whose data is > than current
  575.  * return 0 on success, -1 on failure.
  576.  *
  577.  */
  578. /*ARGSUSED*/
  579. PRIVATE caddr_t
  580. list_insert(head, key, alloc, distance, hint, hint2)
  581. caddr_t *head;
  582. caddr_t key;
  583. caddr_t (*alloc)();
  584. int *distance;
  585. struct hash_chain_item *hint;
  586. struct hash_chain_item *hint2;
  587. {
  588.   struct hash_chain_item *h;
  589.  
  590.   h = (struct hash_chain_item *)malloc(sizeof(struct hash_chain_item));
  591.   if (h == NULL)
  592.     return(NULL);
  593.   h->hci_data = alloc ? (*alloc)(key) : key;
  594.   h->hci_next = hint2;
  595.   if (hint)
  596.     hint->hci_next = h;
  597.   else
  598.     *head = (caddr_t)h;
  599.   return(h->hci_data);
  600. }
  601.  
  602. /*
  603.  * assumes a find has been done, hint is set by find and item exists
  604.  *  in the list
  605.  * head - head of list
  606.  * item - data (unused)
  607.  * hint - previous node to one that contains item
  608.  * distance - distance to update (not done) (may be deleted)
  609.  *
  610. */
  611. /*ARGSUSED*/
  612. PRIVATE int
  613. list_delete(head, key, distance, hint, hint2)
  614. caddr_t *head;
  615. caddr_t key;
  616. int *distance;            /* not used */
  617. struct hash_chain_item *hint;
  618. struct hash_chain_item *hint2;
  619. {
  620.   /* trust our input: two things could be wrong, first */
  621.   /* hint2 == NULL ==> nothing to delete */
  622.   /* hint2 != "key" ==> item not in list */
  623.   if (hint == NULL) {
  624.     *head = (caddr_t)hint2->hci_next;    /* remove */
  625.     free((caddr_t)hint2);
  626.     return(TRUE);
  627.   }
  628.   hint->hci_next = hint2->hci_next; /* unlink */
  629.   free((caddr_t)hint2);        /* get rid of node */
  630.   return(TRUE);
  631. }
  632.  
  633. /* gets first item on list and returns data, freeing up node */
  634. PRIVATE caddr_t
  635. list_get(h)
  636. struct hash_chain_item **h;
  637. {
  638.   struct hash_chain_item *n;
  639.   caddr_t d;
  640.  
  641.   if (h == NULL || *h == NULL)
  642.     return(NULL);
  643.   n = *h;            /* get item */
  644.   *h = n->hci_next;        /* and remove */
  645.   d = n->hci_data;
  646.   free((caddr_t)n);
  647.   return(d);
  648. }
  649.  
  650. /* do hash division method */
  651. /*ARGSUSED*/
  652. PRIVATE u_int
  653. hash_division(M, logM, idx)
  654. int M;
  655. int logM;
  656. u_int idx;
  657. {
  658.   return(idx % M);
  659. }
  660.  
  661. /* will work will with M if M-2,M are twin primes */
  662. /*ARGSUSED*/
  663. PRIVATE u_int
  664. hash2_division(M, logM, hidx, idx)
  665. int M;
  666. int logM;
  667. u_int hidx;
  668. u_int idx;
  669. {
  670.   return(1 + (idx % (M-2)));
  671. }
  672.  
  673. /* handle multiplicative method - hopefully the multiplier gives us */
  674. /* good range */
  675. /*ARGSUSED*/
  676. PRIVATE u_int
  677. hash_multiplicative(M, logM, idx)
  678. int M;
  679. int logM;
  680. u_int idx;
  681. {
  682.   return(((u_int)idx*A_MULTIPLIER>>(8*sizeof(int)-logM)));
  683. }
  684.  
  685. /* the r more bits -- should be indepdent of the first r bits */
  686. /*ARGSUSED*/
  687. PRIVATE u_int
  688. hash2_multiplicative(M, logM, hidx, idx)
  689. int M;
  690. int logM;
  691. u_int hidx;
  692. u_int idx;
  693. {
  694.   return(((u_int)idx*A_MULTIPLIER>>(8*sizeof(int)-logM-logM)|1) );
  695. }
  696.  
  697. #ifdef TESTIT
  698. /* test program */
  699. u_int
  700. docomp(data)
  701. char *data;
  702. {
  703.   u_int j;
  704.   j = 0;
  705.   while (*data)
  706.     j = ((j + *data++) >> 1) | j<<31;
  707.   return(j);
  708. }
  709.  
  710. char *
  711. alloc_func(p)
  712. char *p;
  713. {
  714.   char *d = (caddr_t)malloc(strlen(p) + 1);
  715.   strcpy(d, p);
  716.   return(d);
  717. }
  718.  
  719. dumpstats(msg, s)
  720. char *msg;
  721. struct hash_statistics *s;
  722. {
  723.   printf("%s\n\t %d bkts used, avg dist = %d.%02d, max dist = %d\n",
  724.      msg,
  725.      s->hs_used, s->hs_davg/100, s->hs_davg % 100,
  726.      s->hs_dmax);
  727. }
  728.  
  729. main()
  730. {
  731.   HTABLE *hpc, *hplp, *hpdh;
  732.   extern strcmp();
  733.   char buf[BUFSIZ];
  734.   int b, d, op;
  735.   char *p;
  736.  
  737. #define X 16 
  738.  
  739.   hpc = (HTABLE *)h_new(HASH_POLICY_CHAIN, HASH_TYPE_DIVISION, X,
  740.             strcmp, alloc_func, docomp, NULL, NULL, NULL);
  741.   hplp = (HTABLE *)h_new(HASH_POLICY_LINEAR_PROBE,
  742.              HASH_TYPE_MULTIPLICATIVE, X, strcmp,
  743.              alloc_func, docomp, NULL, NULL, NULL);
  744.   hpdh = (HTABLE *)h_new(HASH_POLICY_DOUBLE_HASH,
  745.              HASH_TYPE_MULTIPLICATIVE, X, strcmp,
  746.              alloc_func, docomp, NULL, NULL, NULL);
  747.   while (gets(buf) != NULL) {
  748.     p = buf+1;
  749.     switch (buf[0]) {
  750.     case '+':
  751.       printf("INSERT %s\n", buf+1);
  752.       op = HASH_OP_INSERT;
  753.       break;
  754.     case '-':
  755.       printf("DELETE %s\n", buf+1);
  756.       op = HASH_OP_DELETE;
  757.       break;
  758.     case ' ':
  759.       printf("FIND %s\n", buf+1);
  760.       op = HASH_OP_MEMBER;
  761.       break;
  762.     default:
  763.       op = HASH_OP_INSERT;
  764.       p = buf;
  765.     }
  766.     if ((h_operation(op, hpc, p, -1, -1, &d, &b)))
  767.       printf("chain: %s at distance %d from bucket %d\n", p, d,b);
  768.     else
  769.       printf("chain hash table overflow or item not in table\n");
  770.     if ((h_operation(op, hplp, p, -1, -1, &d, &b)))
  771.       printf("linear probe: %s at distance %d from bucket %d\n", p, d,b);
  772.     else
  773.       printf("linear probe hash table overflow or item not in table\n");
  774.     if ((h_operation(op, hpdh, p, -1, -1, &d, &b)))
  775.       printf("double hash: %s at distance %d from bucket %d\n", p, d,b);
  776.     else
  777.       printf("double hash table overflow or item not in table\n");
  778.   }
  779.   dumpstats("double hash with multiplicative hash", h_statistics(hpdh));
  780.   h_redefine(hpdh, HASH_POLICY_CHAIN,HASH_TYPE_DIVISION, X, NULL,
  781.          NULL, NULL, NULL,NULL,NULL);
  782.   dumpstats("redefine above as chain with division hash", h_statistics(hpdh));
  783.   h_redefine(hpdh, HASH_POLICY_LINEAR_PROBE,HASH_TYPE_MULTIPLICATIVE,
  784.          X, NULL,NULL,NULL,NULL,NULL,NULL);
  785.   dumpstats("redefine above as linear probe with multiplicative hash",
  786.         h_statistics(hpdh));
  787.   dumpstats("chain with division hash", h_statistics(hpc));
  788.   dumpstats("linear probe with multiplicative hash", h_statistics(hplp));
  789.   h_free(hpdh, free);
  790. }
  791. #endif
  792.